package com.langsin.HeapDemo;

import java.util.Arrays;

/**
 * @Auther: MFM
 * @Date: 2021/8/16 - 08 - 16 - 16:19
 * @version: 1.0
 */

public class HeapSort {
    /**
     * 堆排序方法
     *
     * @param arr 待排序数组
     */
    public static void sort(int[] arr) {
//        adjustHeap(arr,1,arr.length);
//        System.out.println("对第一个非叶子节点的调整："+Arrays.toString(arr));
//
//        adjustHeap(arr,0,arr.length);
//        System.out.println("对第二个非叶子节点的调整："+Arrays.toString(arr));

        int tmp = 0;

        for (int i = arr.length / 2 - 1 ,j = 1; i >= 0; i--,j++) {
            adjustHeap(arr,i,arr.length);
        }

        for (int i = arr.length-1; i >0 ; i--) {
            tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            adjustHeap(arr,0,i);
        }
    }

    /**
     * 将一个普通堆变成大根堆
     * 注意：先从下到上 从左到右 进行调整的
     *
     * @param arr    需要调整的数组
     * @param i      从哪一个非叶子节点开始调整
     * @param length 对多少个元素进行调整
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int tmp = arr[i];//临时变量，保存当前父节点的值

        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            //先判断两个子节点谁大，然后用大的去跟父节点来比较
            if (k + 1 < length && arr[k] < arr[k + 1]) {//加入左边的比右边的小
                k++;//那么让右边的与父节点比较
            }
            if (arr[k] > tmp) {//如果子节点较大的一个比父节点大
                arr[i] = arr[k];//把较大的赋值给当前节点
                i = k;//进行循环比较
            } else {
                break;//注意：先从下到上 从左到右 进行调整的
            }
        }

        arr[i] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
